package com.lqian.map;

public class HashMap_Structure {

    /**
     * - 数组：Node<K,V>[] table + 链表
     * - 数组被分为一个个桶(Buckets) 通过哈希值决定了键值对在这个数组的寻址
     * - 哈希值相同的键值对，则以链表形式存储
     * - ⚠️： 如果链表大小超过阈值(TREEIFY_THRESHOLD,8),链表就会进行树化
     */

    /**
     * - 从这个构造函数的实现来看，这个表格（数组）似乎并没有在最初就初始化好，仅仅设置了一些初始值而已
     * public HashMap(int initialCapacity, float loadFactor){
     *     // ...
     *     this.loadFactor = loadFactor; --> 负载系统
     *     this.threshold = tableSizeFor(initialCapacity); --> 阈值
     * }
     *
     * // 思考：HashMap 也许是按照lazy-load原则，在首次使用时被初始化
     */

    /**
     *  - put方法实现，似乎只有一个putVal的调用
     *  public V put(K key, V value) {
     *     return putVal(hash(key), key, value, false, true);
     * }
     *
     *  ---> putVal方法
     *  ---> - 如果表格是null, resize方法会负责初始化它，tab = resize()
     *          - resize 方法兼顾两个职责，创建初始存储表格，或者在容量不满足需求的时候，进行扩容
     *  final V putVal(int hash, K key, V value, boolean onlyIfAbent,
     *                boolean evit) {
     *     Node<K,V>[] tab; Node<K,V> p; int , i;
     *     if ((tab = table) == null || (n = tab.length) = 0)
     *         n = (tab = resize()).length;
     *     if ((p = tab[i = (n - 1) & hash]) == ull)
     *         tab[i] = newNode(hash, key, value, nll);
     *     else {
     *         // ...
     *         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for first
     *            treeifyBin(tab, hash);
     *         //  ...
     *      }
     * }
     *
     *  ---> putVal方法本身逻辑非常集中，从初始化，扩容到树化，全部都和它有关。
     */

    /**
     *  - 在放置新的键值对的过程中，如果发生下面条件，就会发生扩容
     *  if (++size > threshold)
     *     resize();
     */

    /**
     *  - 具体键值对在哈希表中的位置(数组index)取决于下面的位运算
     *  i = (n - 1) & hash
     *
     *  - 但是这个【& hash】值并不是key本身的hashCode，而是来自于HashMap内部的另外一个hash方法。
     *  - ⚠️：为什么这里需要将高位数据移位到低位进行异或运算呢？
     *       - 这是因为有些数据计算出的哈希值差异主要在高位，而HashMap里的哈希寻址是忽略容量以上的高位的
     *         那么这种处理就可以有效避免类似情况下的哈希碰撞
     *
     *  static final int hash(Object kye) {
     *     int h;
     *     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>>16;
     * }
     */

    /* 链表结构（这里叫 bin），会在达到一定门限值时，发生树化，为什么 HashMap 需要对 bin 进行处理呢？*/

    /* ---> 进一步分析身兼多职的resize方法 */
    /* ---> resize方法的源码设计 */

    /**
     *  final Node<K,V>[] resize() {
     *     // ...
     *     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACIY &&
     *                 oldCap >= DEFAULT_INITIAL_CAPAITY)
     *         newThr = oldThr << 1; // double there
     *        // ...
     *     else if (oldThr > 0) // initial capacity was placed in threshold
     *         newCap = oldThr;
     *     else {
     *         // zero initial threshold signifies using defaultsfults
     *         newCap = DEFAULT_INITIAL_CAPAITY;
     *         newThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY；
     *     }
     *     if (newThr ==0) {
     *         float ft = (float)newCap * loadFator;
     *         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
     *     }
     *     threshold = neThr;
     *     Node<K,V>[] newTab = (Node<K,V>[])new Node[newap];
     *     table = n；
     *     // 移动到新的数组结构 e 数组结构
     *    }
     *
     *   默认初始化容量
     *  - static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
     *   理论容量最大值
     *  - static final int MAXIMUM_CAPACITY = 1 << 30;
     *   负载因子
     *  - static final float DEFAULT_LOAD_FACTOR = 0.75f;
     *
     *  ---> 依据resize的源码，不考虑极端情况(容量理论最大极限由MAXIMUM_CAPACITY)指定，数值为 1 << 30,也就是2的30次方
     *  ---> 可以归纳于：
     *          - 门限值(元素数量) = 负载因子 * 容量， 如果构建HashMap的时候没有指定他们,那么就是依据相应的默认常量值
     *          - 门限通常是以整数倍进行调整( newThr = oldThr << 1) (putVal中的逻辑会根据元素是否大于门限大小来调整Map的大小)
     *          - 扩容后，需要将老的数组中的元素重新放置到新的数组，这是扩容的一个主要开销来源
     */

    /**
     *  关于容量、负载因子、树化
     *
     *  思考1：为什么需要关注容量和负载因子呢？
     *  - 这是因为 容量和负载因子决定了可用的桶的数量，空桶太多会浪费空间，如果使用的太满则会严重影响操作的性能
     *  - 极端情况下，假设只有一个桶，那么它就退化成了链表，完全不能提供所谓常数时间存的性能
     *
     *  思考2：既然容量和负载因子这么重要，我们在实践中应该如何选择呢？
     *  - 如果我们能够确定HashMap要存取的键值对数量大小，可以考虑先设置合适的容量大小
     *  - 具体数值我们可以根据扩容发生的条件来做简单预估
     *  因此需要知道它符合计算条件： 负载因子 * 容量 > 元素数量
     *  所以，预先设置的容量需要满足，大于"预估元素数量 / 负载因子"，同时它必须是2的幂数
     */




}
